//1883. 准时抵达会议现场的最小跳过休息次数

https://leetcode.cn/problems/minimum-skips-to-arrive-at-meeting-on-time/?envType=daily-question&envId=Invalid%20Date

class Solution {
  int speed;
  long rest(long start) {
  if (start % speed == 0)
    return start;
  else return (start/speed + 1)*speed;
}
public:
  int minSkips(vector<int> &dist, int speed, int hoursBefore) {
    int numN = dist.size();
    this->speed = speed;
    vector<long> dp(numN);
    vector<long> dp_after(numN);
    dp[0] = dist[0];
    for (int i = 1; i < numN; i++) {
      dp[i] = rest(dp[i-1])+dist[i];
    }
    if(dp[numN-1]<=(long)hoursBefore*speed)return 0;
    dp_after[0] = dp[0];
    for(int i=1;i<numN;i++){
      for(int j=1;j<numN;j++){
        long restAndDrive = rest(dp_after[j-1])+dist[j];
        long dontRestThisTime = dp[j-1] + dist[j]; 
        dp_after[j] = min(restAndDrive,dontRestThisTime);
      }
      if(dp_after[numN-1]<=hoursBefore*speed)return i;
      dp = dp_after;
    }
    return -1;
  }
};